package 字符串;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * @Author Weton Li
 * @Date 2021/4/1 18:29
 */
public class 字符串第一个唯一字符 {

    public static int method(String s) {
        HashMap<Character, Integer> map = new HashMap<>();

        int i = 0;
        while (i < s.length()) {
            char c = s.charAt(i);
            // 不论是否在map中已经出现过此字符，均会+1操作。默认为0，出现一个即+1代表
            // 如果我想获取一个map中已经放置的k所对应的v值，但当我发现map中并没有放置此k，此时给此k对应的v一个默认值0
            map.put(c, map.getOrDefault(c, 0) + 1);
//            System.out.println(j);

            i++;
        }

        int j = 0;
        while (j < s.length()) {
            if (map.get(s.charAt(j)) == 1) { // 遍历字符串每个字符，将其字符作为k，获取对应v，和1（只出现了一次）进行比较，当满足即为第一个唯一字符。
                return j;
            }
            j++;
        }

        return -1;
    }


    public static void main(String[] args) {
        String input = "loveleetcode"; // v最先没有出现
        System.out.println(method(input));
        System.out.println(firstUniqChar(input));
    }


    public static int firstUniqChar(String s) {
        Map<Character, Integer> position = new HashMap<Character, Integer>();
        Queue<Pair> queue = new LinkedList<Pair>();
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            char ch = s.charAt(i);
            if (!position.containsKey(ch)) {
                position.put(ch, i); // 该集合记录字符下标位置
                queue.offer(new Pair(ch, i)); // 将当前字符和位置 存队列（队列里存对象，对象有两个属性）
            } else {
                position.put(ch, -1); // 将重复出现的字符对应的value变为-1
                // 如果队首元素为-1，我才删除。// 使用while是为了防止当map中已有多个映射的value被put为-1，队首元素弹出后，下一个队首元素的仍为-1
                while (!queue.isEmpty() && position.get(queue.peek().ch) == -1) {
                    queue.poll();
                }
            }
        }
        return queue.isEmpty() ? -1 : queue.poll().pos;
    }


    static class Pair {
        char ch;
        int pos;

        Pair(char ch, int pos) {
            this.ch = ch;
            this.pos = pos;
        }
    }
}

